/* 
 *
 * Electric(tm) VLSI Design System
 *
 * File: MinAreaCheckerImplementation.scala
 * Written by: Daniel Schmidt
 * 
 * This code has been developed at the Karlsruhe Institute of Technology (KIT), Germany, 
 * as part of the course "Multicore Programming in Practice: Tools, Models, and Languages".
 * Contact instructor: Dr. Victor Pankratius (pankratius@ipd.uka.de)
 *
 * Copyright (c) 2011, Oracle and/or its affiliates. All rights reserved.
 *
 * Electric(tm) is free software; you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation; either version 3 of the License, or
 * (at your option) any later version.
 *
 * Electric(tm) is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with Electric(tm); see the file COPYING.  If not, write to
 * the Free Software Foundation, Inc., 59 Temple Place, Suite 330,
 * Boston, Mass 02111-1307, USA.
 */
package com.sun.electric.plugins.minarea.mk01

import java.util.BitSet
import java.util.HashMap
import java.util.Properties
import scala.actors.Futures
import com.sun.electric.api.minarea.ErrorLogger
import com.sun.electric.api.minarea.LayoutCell
import com.sun.electric.api.minarea.ManhattanOrientation
import com.sun.electric.api.minarea.MinAreaChecker
import com.sun.electric.plugins.minarea.mk01.Layout.FlattenHandler
import com.sun.electric.plugins.minarea.mk01.Layout.ReduceElementsHandler


class MinAreaCheckerImplementation extends MinAreaChecker{
  
  /** DEBUG mode on/off */
  val DEBUG = false

  /** see specification */
  var errorLogger : ErrorLogger = null
  
  /** see specification */
  var minArea : Long = 0
  
  /** Indicates whether all actors of phase 3 have finished */
  var finished = false
  
  /** see specification */
  override def getAlgorithmName = "mk01"

  /** see specification */
  override def getDefaultParameters = {
    val parameters = new Properties()
    parameters.put(MinAreaChecker.REPORT_TILES, java.lang.Boolean.TRUE)
    parameters.put(MinAreaChecker.NUM_THREADS, 4: Integer)
    parameters
  }

  /**
   * @param topCell top cell of the layout
   * @param minArea minimal area of valid polygon
   * @param parameters algorithm parameters
   * @param errorLogger an API to report violations
   */
  override def check(topCell: LayoutCell, minArea: Long, parameters: Properties, errorLogger: ErrorLogger) = {

    //initialize
    val reportTiles = java.lang.Boolean.parseBoolean(parameters.get(MinAreaChecker.REPORT_TILES).toString)
    val numOfThreads = java.lang.Integer.parseInt(parameters.get(MinAreaChecker.NUM_THREADS).toString())
    this.errorLogger = errorLogger
    this.minArea = minArea
    this.finished = false
    
    
    //Phase 1
    
    val startPhaseOne = System.currentTimeMillis()
    
    //Collect all unique x and y coordinates of rectangle's edges
    val reduceElements: ReduceElementsHandler = new ReduceElementsHandler(numOfThreads, DEBUG)
    
    reduceElements.start(topCell, 0, 0, ManhattanOrientation.R0)
    
    var setOfXCoordinates = reduceElements.getSetOfXCoordinates()
    var setOfYCoordinates = reduceElements.getSetOfYCoordinates()
    
    val xsize = setOfXCoordinates.size - 1
    val ysize = setOfYCoordinates.size - 1
    
    //Create two maps : 1. Map index to coordinate 2. Map coordinate to index
    val indexToXCoordinate = new Array[Int](xsize + 1)
    val indexToYCoordinate = new Array[Int](ysize + 1)
    val xCoordinateToIndex = new HashMap[Int, Int]()
    val yCoordinateToIndex = new HashMap[Int, Int]()

    val it1 : java.util.Iterator[Int] = setOfXCoordinates.iterator()
    val mapX = Futures.future {
      while(it1.hasNext()) {
        val x = it1.next()
        indexToXCoordinate(xCoordinateToIndex.size) = x
        xCoordinateToIndex.put(x, xCoordinateToIndex.size)
      }
    }

    val it2 : java.util.Iterator[Int] = setOfYCoordinates.iterator()
    val mapY = Futures.future {
      while(it2.hasNext()) {
        val y = it2.next()
        indexToYCoordinate(yCoordinateToIndex.size) = y
        yCoordinateToIndex.put(y, yCoordinateToIndex.size)
      }
    }
    
    Futures.awaitAll(6000*6000*6000, mapX, mapY)
    
    val endPhaseOne = System.currentTimeMillis()
    
    if (DEBUG) {
      println("number of x coordinates = " + xsize);
      println(setOfXCoordinates)
      println("number of y coordinates = " + ysize)
      println(setOfYCoordinates)
    }
    
    //Phase 2
    
    val startPhaseTwo = System.currentTimeMillis()
    
    //initializie bitmap
    val bitMap = new Array[BitSet](xsize)
    for (i <- 0 until bitMap.length) {
      bitMap(i) = new BitSet
    }
    
    //flatten the layout and create the bitmap
    val flattenLayout: FlattenHandler = new FlattenHandler(numOfThreads, xCoordinateToIndex, yCoordinateToIndex, bitMap, DEBUG)
    flattenLayout.start(topCell, 0, 0, ManhattanOrientation.R0)
    
    val endPhaseTwo = System.currentTimeMillis()
    
    if(DEBUG) {
      println("BitMap: ")
      var y = ysize 
      while (y >= 0) {
        for (x <- 0 until xsize) print(if (bitMap(x).get(y)) 'X' else '0')
        println
        y -= 1
      }
    }
    
    //Phase 3
    
    val startPhaseThree = System.currentTimeMillis()
    
    /*
     * The Phase 3 algorithm divides the whole bitmap in multiple plots (amount of columns).
     * Each plot is checked by an individual actor in parallel and the result are merged
     * afterwards.
     */
    val columns = Math.min(numOfThreads, bitMap.length)
    val step : Float = xsize.toFloat / columns
    var lastTraverser : BitmapTraverser = null
    var counter = columns
    var start = xsize
    
    var worker = new Array[BitmapTraverser](columns)
    while(counter > 0) {
      
      //Determine working range for each actor
      val end = start - 1
      if(counter > 1) {
        start = Math.round((counter - 1).toFloat * step)
      } else {
        start = 0
      }
      
      /*
       * The bitmap gets cleared during execution. To ensure that later actors 
       * may still find the connections to the left or right plot, the actors 
       * get a copy of the border bitsets (leftBorder is the most right bitset of
       * the left plot - rightBorder is the most left bitset of the right plot)
       */
      val leftBorder : BitSet = new BitSet
      val leftBorderValue = Math.max(0, start - 1)
      leftBorder.or(bitMap(leftBorderValue))
      val rightBorder : BitSet = new BitSet
      val rightBorderValue = Math.min(bitMap.length - 1, end + 1)
      rightBorder.or(bitMap(rightBorderValue))
      
      if(counter < worker.length) {
        lastTraverser = worker(counter)
      }
      
      //create actor
      worker(counter-1) = new BitmapTraverser(this, counter - 1, start, end, bitMap, 
          indexToXCoordinate, indexToYCoordinate, leftBorder, rightBorder, lastTraverser)
      
      counter = counter - 1
    }
    
    //and start him
    for(traverser <- worker) {
      traverser.start()
      Thread.sleep(20)
    }
    
    //Wait for all working actors
    while(!finished) {
      Thread.sleep(100)
    }
 
    val endPhaseThree = System.currentTimeMillis()
    
    if(DEBUG) {
      println("Execution time of Phase 1 : " + (endPhaseOne - startPhaseOne))
      println("Execution time of Phase 2 : " + (endPhaseTwo - startPhaseTwo))
      println("Execution time of Phase 3 : " + (endPhaseThree - startPhaseThree))
    }
  }
  
  /**
   * Sets the phase 3 process on finished
   */
  def setFinished() = {
    finished = true
  }
  
  /**
   * Returns the error logger
   */
  def getErrorLogger() = errorLogger
  
  /**
   * Returns the min area
   */
  def getMinArea() = minArea
}
